Cos'è spanning tree?

Spanning Tree (Albero Ricoprente)

Uno spanning tree (in italiano, "albero ricoprente") di un grafo connesso non orientato è un sottografo che è un albero e che connette tutti i vertici del grafo originale. In altre parole, è un sottoinsieme degli archi del grafo originale che forma un albero che "ricopre" tutti i vertici. Un grafo connesso può avere molti spanning tree diversi.

Concetti chiave: